package dp;

/**
 * @author tmh
 * @date 2024/9/15 16:35
 * @description
 */
public class T96不同的二叉搜索树 {
    //dp[i]:1到i分别为头节点组成的二叉搜索树的个数之和为dp[i]
    //dp[i]=dp[i]+dp[j-1]*dp[i-j]
    public int numTrees(int n) {
        if (n < 3) {
            return n;
        }
        int[] dp = new int[n + 1];
        //初始化
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                //j:j作为根节点； 一开始dp[i]的值为0,把所有以j为头节点的个数相加就是我们最后的dp[i]
                //可以这样理解:右面的dp[i]存储上次的结果，左面的的dp[i]来存储最后的结果
                //dp[j-1]:左子树的节点
                //dp[i-j]:右子树的节点
                dp[i] = dp[i] + dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}
